/* sHT - iterate over indices
   Copyright (C) 2019 Ariadne Devos

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

#ifndef _sHT_INDEX_H
#define _sHT_INDEX_H

/** Array indices

  This module counts from 0 to any number. It eliminates most off-by-one
  errors, ensures the index is within bounds on out-of-order architectures
  (see Spectre) and results in very clear and terse code.

  Academic paper on Spectre: https://spectreattack.com (2018).
  Practical news articles on Spectre: https://lwn.net/Kernel/Index (2018-2019).
*/

#include <sHT/nospec.h>
#include <sHT/test.h>
#include <stddef.h>

/** Check that the variable @var{i} may be used as an index.

  It must be a @var{size_t}. */
#define sHT_index_check(i) \
	_Static_assert(_Generic(*&(i), size_t: 1, default: 0), \
		"size_t is an appropriate type for indices")

/** Check that the expression @var{n} may be used as an array length.

  All unsigned integral types are fine. */
#define sHT_size_check(n) \
	_Static_assert(_Generic((n), unsigned: 1, unsigned long: 1, \
		unsigned long long: 1, default: 0), \
		"size_t is an appropriate type for lengths")

/** Iterate @var{i} from 0 (inclusive) to @var{n} (exclusive), in that
  order.

  @var{i}: a loop counter / index variable. Its initial value, if any, is unused.
    It must be a size_t, which is checked at compile-time.
  @var{n}: the nominal number of iterations to do, less than @var{SSIZE_MAX}.
    It must be integral, which is checked at compile-time.
    It must be constant.

  A lower number of iterations may be done speculatively. Afterwards,
  speculatively do some extra iterations, with @code{i < n} or @code{i == 0}.
  Non-speculatively, after a normal loop exit, @var{i} equals @var{n}.
  Speculatively, @var{i} will always be less than @var{n} within an iteration
  and never be greater than @var{n}. If the end value is @var{j}, at least
  @var{j} iterations have been done.

  @code{break} and @var{continue} keep their usual semantics.

  This iterator is preferred above a manual for-loop, because comparison
  operator is always correct, the index always is within bounds, even
  on out-of-order microarchitectures and it can be annotated for formal
  analysis.

  TODO: on x86, @code{i < n} is tested twice: when @var{sHT_index_nospec}
  computes the mask, and in the exit condition. Create a specialised copy. */
#define sHT_index_iterate(i, n) \
	sHT_index_check(i); \
	sHT_size_check(n); \
	for ((i) = 0; sHT_gt((n), (i)) ? ((i) = sHT_index_nospec((i), (n))), 1 : 0; (i)++)

#endif
